<!DOCTYPE html>
<html>

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <link rel="stylesheet" href="css/prism.css">
  <style>
    html,
    body {
      box-sizing: border-box;
      margin: 0;
      padding: 0;
      height: 100%;
      font-size: 12px;
    }

    body {
      min-height: 500px;
    }

    section {
      display: flex;
      flex-wrap: wrap;
    }

    .code {
      margin-top: 3px;
    }

    pre[class*=language-] {
      margin: 0;
      padding: 0;
    }

    main {
      border-top: 2px solid #ccc;
      width: 100%;
      height: 74%;
      min-height: 200px;
    }
  </style>
  <title>二叉树遍历(非递归)</title>
</head>

<body>
  <section class="frames"></section>
  <section style="display: none;">
    <pre><code class="language-java">int factorial(int n) {
    if (n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}</code></pre>
  </section>
  <main></main>
  <section>
    <div style='background-color:#00FF99; margin: 2px 2px 0 0; padding: 4px 6px;'>已访问</div>
    <div style='background-color:#ccc; margin: 2px 2px 0 0; padding: 4px 6px;'>未访问</div>
  </section>
  <div style='margin: 2px 2px 0 0; padding: 4px 6px;'>
    <span>数组表示的二叉树&nbsp;</span><input type="text" id='data' class="saveable narray" value="1,2,3,4,n,5,6">
    <span>n&nbsp;</span><input type="text" id='n' class="saveable" value="5">
    <input style='font-size:12px;' type="button" value="前序" onclick="p1()">
    <input style='font-size:12px;' type="button" value="中序" onclick="p2()">
    <input style='font-size:12px;' type="button" value="后序" onclick="p3()">
  </div>
  <div style='margin: 2px 2px 0 0; padding: 4px 6px;'>
    <span>动画速度(ms)&nbsp;</span><input type="number" step="100" value="300" id="animate_speed" class="saveable int"
      style="width: 40px;">
    <span>直径</span><input type="number" step="1" value="50" id="DIAMETER" class="saveable int" style="width: 40px;">
    <input style='font-size:12px;' type="button" value="保存" onclick="onSave('tree_binary2')">
  </div>
  <div id="preDiv"
    style="display: none; padding: 10px 30px 10px 10px; background-color: bisque; position: absolute; top: 100px; right: 0;">
    <span>前序遍历规则</span>
    <ul>
      <li>先访问该节点</li>
      <li>然后是左子树</li>
      <li>最后是右子树</li>
    </ul>
    <span>结果：</span><span class="result"></span>
  </div>
  <div id="inDiv"
    style="display: none; padding: 10px 30px 10px 10px; background-color: bisque; position: absolute; top: 100px; right: 0;">
    <span>中序遍历规则</span>
    <ul>
      <li>先访问左子树</li>
      <li>然后是该节点</li>
      <li>最后是右子树</li>
    </ul>
    <span>结果：</span><span class="result"></span>
  </div>
  <div id="postDiv"
    style="display: none; padding: 10px 30px 10px 10px; background-color: bisque; position: absolute; top: 100px; right: 0;">
    <span>后序遍历规则</span>
    <ul>
      <li>先访问左子树</li>
      <li>然后是右子树</li>
      <li>最后是该节点</li>
    </ul>
    <span>结果：</span><span class="result"></span>
  </div>
  <script src="js/p5.js"></script>
  <script src="js/p5-svg.js"></script>
  <script src="js/util.js"></script>
  <script src="js/prism.js"></script>
  <script>
    const preDiv = document.getElementById("preDiv")
    const inDiv = document.getElementById("inDiv")
    const postDiv = document.getElementById("postDiv")
    const resultSpans = document.querySelectorAll(".result")
    const result = []
    function p1() {
      clearStatus(root)
      result.splice(0)
      preOrder(root)
      d.updateFrameButtons()
      resultSpans[0].innerHTML = result
      preDiv.style.display = "block"
      inDiv.style.display = "none"
      postDiv.style.display = "none"
    }
    function p2() {
      clearStatus(root)
      result.splice(0)
      inOrder(root)
      d.updateFrameButtons()
      resultSpans[1].innerHTML = result
      preDiv.style.display = "none"
      inDiv.style.display = "block"
      postDiv.style.display = "none"
    }
    function p3() {
      clearStatus(root)
      result.splice(0)
      postOrder(root)
      d.updateFrameButtons()
      resultSpans[2].innerHTML = result
      preDiv.style.display = "none"
      inDiv.style.display = "none"
      postDiv.style.display = "block"
    }
    const options = loadOptionsFromStorage('tree_binary2')
    let data = options.data
    console.log(data)
    const DIAMETER = options.DIAMETER
    const LEFT_PAD = 20
    const TOP_PAD = 200
    const n = options.n
    const d = new Draw(options.animate_speed)
    let root

    function setup() {
      const WIN_WIDTH = document.querySelector('main').clientWidth
      const WIN_HEIGHT = document.querySelector('main').clientHeight
      const FONT_SIZE = 10
      createCanvas(WIN_WIDTH, WIN_HEIGHT, SVG)
      textSize(FONT_SIZE)
      textAlign(CENTER)
      root = binary_tree(data, n)
      d.updateFrameButtons()
    }
    function draw() {
      d.draw(() => background('#eee'))
    }
    // curr 当前节点, left 处理谁的左孩子, right 处理谁的右孩子
    function frame({ cloned, array, curr, left, right, pop }) {
      drawTree(cloned, width / 2, DIAMETER, n - 1, 0, 0, curr, left, right, pop)
      if (array) {
        let x = width / 2 - DIAMETER / 2, y = height - DIAMETER
        for (let i = 0; i < array.length; i++) {
          stroke(0)
          fill('#67cdcc')
          rect(x, y, DIAMETER, DIAMETER)
          fill('#ffffff')
          noStroke()
          text(array[i], x + DIAMETER / 2, y + DIAMETER / 2 + 4)
          y -= DIAMETER
        }
      }
    }

    function drawTree(node, x, y, deep, px, py, curr, left, right, pop) {
      if (node) {
        if (node.txt) {
          if (px && py) {
            stroke('black')
            line(x, y, px, py)
          }
        }
        drawTree(node.left, x - Math.pow(2, deep) * DIAMETER / 4, y + Math.pow(2, n - deep) * DIAMETER / 2, deep - 1, x, y, curr, left, right, pop)
        drawTree(node.right, x + Math.pow(2, deep) * DIAMETER / 4, y + Math.pow(2, n - deep) * DIAMETER / 2, deep - 1, x, y, curr, left, right, pop)
        if (node.txt) {
          if (node.txt === curr) {
            fill('#f08d49')
            circle(x, y, DIAMETER + 6)
          }
          if (node.txt === pop) {
            fill('#67cdcc')
            circle(x, y, DIAMETER + 6)
          }
          // console.log(node.status, (node.status & 1) === 1, (node.status & 2) === 2, (node.status & 4) === 4)
          if ((node.status & 1) === 1) { fill('#00FF99') } else { fill('#ccc') }
          arc(x, y, DIAMETER, DIAMETER, PI, TWO_PI)
          if ((node.status & 2) === 2) { fill('#00FF99') } else { fill('#ccc') }
          arc(x, y, DIAMETER, DIAMETER, HALF_PI, PI)
          if ((node.status & 4) === 4) { fill('#00FF99') } else { fill('#ccc') }
          arc(x, y, DIAMETER, DIAMETER, 0, HALF_PI)

          if (node.txt === left) {
            fill('#f08d49')
            arc(x, y, DIAMETER, DIAMETER, HALF_PI, PI)
          }
          if (node.txt === right) {
            fill('#f08d49')
            arc(x, y, DIAMETER, DIAMETER, 0, HALF_PI)
          }
          fill('black')
          text(node.txt, x, y - 2)
        }
      }
    }

    function preOrder(node) {
      const stack = []
      let curr = node
      let left = null
      let right = null
      while (stack.length > 0 || curr != null) {
        d.add({ cloned: clone(root), array: stack.map(e => e.txt), curr: curr ? curr.txt : 'null', left, right }, frame)
        if (curr) {
          stack.push(curr)
          curr.status |= 1
          result.push(curr.txt)
          d.add({ cloned: clone(root), array: stack.map(e => e.txt), curr: curr ? curr.txt : 'null' }, frame)
          left = curr.txt
          right = null
          curr = curr.left
        } else {
          const pop = stack.pop()
          curr = pop.right
          left = null
          right = pop.txt
        }
      }
      d.add({ cloned: clone(root), array: stack.map(e => e.txt), curr: curr ? curr.txt : 'null', left, right }, frame)
      d.add({ cloned: clone(root), array: stack.map(e => e.txt), curr: curr ? curr.txt : 'null' }, frame)
    }

    function inOrder(node) {
      const stack = []
      let curr = node
      let left = null
      let right = null
      while (stack.length > 0 || curr != null) {
        d.add({ cloned: clone(root), array: stack.map(e => e.txt), curr: curr ? curr.txt : 'null', left, right }, frame)
        if (curr) {
          stack.push(curr)
          left = curr.txt
          right = null
          curr = curr.left
        } else {
          const pop = stack.pop()
          pop.status |= 1
          result.push(pop.txt)
          d.add({ cloned: clone(root), array: stack.map(e => e.txt), curr: curr ? curr.txt : 'null' }, frame)
          curr = pop.right
          left = null
          right = pop.txt
        }
      }
      d.add({ cloned: clone(root), array: stack.map(e => e.txt), curr: curr ? curr.txt : 'null', left, right }, frame)
      d.add({ cloned: clone(root), array: stack.map(e => e.txt), curr: curr ? curr.txt : 'null' }, frame)
    }

    function postOrder(node) {
      const stack = []
      let curr = node
      let pop = null
      let left = null
      let right = null
      while (stack.length > 0 || curr != null) {
        d.add({ cloned: clone(root), array: stack.map(e => e.txt), curr: curr ? curr.txt : 'null', left, right, pop: pop ? pop.txt : 'null', keyframe: pop && right == null && left == null ? true : false }, frame)
        if (curr) {
          stack.push(curr)
          left = curr.txt
          right = null
          curr = curr.left
        } else {
          const peek = stack[stack.length - 1]
          left = null
          right = peek.txt
          if (peek.right && peek.right != pop) {
            curr = peek.right
          } else {
            d.add({ cloned: clone(root), array: stack.map(e => e.txt), curr: curr ? curr.txt : 'null', left, right, pop: pop ? pop.txt : 'null' }, frame)
            right = null
            pop = stack.pop()
            pop.status |= 1
            result.push(pop.txt)
          }
        }
      }
      d.add({ cloned: clone(root), array: stack.map(e => e.txt), curr: curr ? curr.txt : 'null', pop: pop ? pop.txt : 'null', keyframe: pop && right == null && left == null ? true : false }, frame)
    }

    function clearStatus(node) {
      if (!node) {
        return
      }
      node.status = 0
      clearStatus(node.left)
      clearStatus(node.right)
    }

    /*
      status
        0-都未处理
        1-节点自身处理完
        2-左孩子处理完
        4-右孩子处理完
    */
    // 根据 array 构造二叉树
    function binary_tree(array, n) {
      const newArray = array.map(e => e ? ({ txt: e, status: 0 }) : null)
      const size = array.length
      for (let i = size - 1; i > 0; i--) {
        const pi = (i - 1) >> 1
        const parent = newArray[pi]
        if (parent != null) {
          const left = 2 * pi + 1
          const right = left + 1
          if (left === i) {
            parent.left = newArray[i]
          }
          if (right === i) {
            parent.right = newArray[i]
          }
        }
      }
      const root = newArray[0]
      d.add({ cloned: clone(root) }, frame)
      return root
    }

    function clone(tree) {
      return JSON.parse(JSON.stringify(tree))
    }

  </script>
</body>

</html>